package com.cty._03_SolutionSeekingMindset._34_PathInTree;

import java.util.ArrayList;
import java.util.List;

/**
 * @Auther: cty
 * @Date: 2020/7/13 9:56
 * @Description: 面试题34：二叉树中和为某一值的路径
 * 题目：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所
 * 有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 * @version: 1.0
 */
public class PathInTree {

    public static void findPath(BinaryTreeNode treeRoot, int expect){
        if(treeRoot == null)
            return;

        List<Integer> list = new ArrayList<>();
        int current = 0;
        recFindPath(treeRoot, list, expect, current);
    }

    private static void recFindPath(BinaryTreeNode treeNode, List<Integer> list, int expect, int current){
        list.add(treeNode.value);
        current += treeNode.value;

        if(current == expect) {
            for (int value : list)
                System.out.print(value + " ");
            System.out.println();
            list.remove(list.size()-1);
            return;
        }

        if(current > expect){
            list.remove(list.size()-1);
            return;
        }

        // real < expect
        if(treeNode.leftChild != null)
            recFindPath(treeNode.leftChild, list, expect, current);

        if(treeNode.rightChild != null)
            recFindPath(treeNode.rightChild, list, expect, current);

        list.remove(list.size()-1);
    }  // end recFindPath()

}  // end class

class BinaryTreeNode{
    int value;
    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;

    public BinaryTreeNode(){}

    public BinaryTreeNode(int value){this.value = value;}
}  // end class
